package main

import "fmt"

//type ListNode struct {
//	Val  int
//	Next *ListNode
//}

func main() {
	getIntersectionNode(&ListNode{4, &ListNode{1, &ListNode{8, &ListNode{4, &ListNode{5, nil}}}}}, &ListNode{5, &ListNode{0, &ListNode{1, &ListNode{8, &ListNode{4, &ListNode{5, nil}}}}}})
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lengthA := getListLength(headA)
	lengthB := getListLength(headB)
	fmt.Println(lengthB, lengthA)
	if lengthB > lengthA {
		headB = moveNode(headB, lengthB-lengthA)
	} else {
		headA = moveNode(headA, lengthA-lengthB)
	}
	for headB != nil && headA != nil {
		if headB == headA {
			return headB
		} else {
			headB = headB.Next
			headA = headA.Next
		}
	}
	return nil
	//mapListNode := make(map[ListNode]*ListNode)
	//
	//for headA != nil {
	//	mapListNode[*headA] = headA
	//	headA = headA.Next
	//}
	//for headB != nil {
	//	if mapListNode[*headB] == headB {
	//		return headB
	//	}
	//	mapListNode[*headB] = headB
	//	headB = headB.Next
	//}
	//return nil
}

func getListLength(head *ListNode) int {
	length := 0
	for head != nil {
		length++
		head = head.Next
	}
	return length
}

func moveNode(head *ListNode, length int) *ListNode {
	for i := length; i > 0; i-- {
		head = head.Next
	}
	return head
}
